Задача о письмах

Рис. 1

Пусть n = 5. Сопоставим каждому знакомому Кати точку на плоскости и проведем стрелочки от одних точек к другим в зависимости от того, кому чье письмо досталось. Получающуюся картинку математики называют (ориентированным) графом, точки — вершинами графа, а стрелочки — ребрами графа. Например, граф, изображенный на рис. 1, соответствует ситуации, когда письмо, адресованное первому знакомому, попало пятому знакомому; письмо, адресованное второму, попало четвертому; письмо, адресованное третьему, попало первому; и так далее.

Рис. 2

Из условия задачи следует, что из каждой вершины выходит ровно одна стрелочка и в каждую вершину входит ровно одна стрелочка. Следовательно, наш граф является объединением нескольких циклов. Поскольку ни один из Катиных друзей не получил письма, адресованного ему, в графе нет петель, то есть циклов длины 1 (стрелочек, ведущих от вершины в саму себя). Поэтому для устройства графа есть ровно две возможности: либо он является одним циклом длины 5 (как на рис. 2), либо он распадается на два цикла, один из которых имеет длину 3, а второй — длину 2 (как на рис. 1)

Итак, каждый способ рассылки писем соответствует некоторому графу одного из указанных выше двух видов. Осталось выяснить, сколько различных графов каждого вида может быть.

Пусть F_n означает число способов, которыми Катя могла сделать полную путаницу в том случае, когда число ее знакомых равно n. Наша цель — найти F₁₅.

Попробуйте выразить F_n через F_n–1, F_n–2, F_n–3, ... . Тогда, вычислив первые несколько значений последовательности F₁, F₂, F₃, ... вручную, последующие ее члены (вплоть до F₁₅) можно было бы посчитать при помощи найденной формулы.

Докажите, что F_n = (n – 1)(F_n–1 + F_n–2)

а) Как мы выяснили, нам нужно найти количество различных графов с пятью вершинами, которые представляют собой либо цикл длины 5, либо объединение двух циклов длины 2 и 3.

Вычислим сначала, сколько бывает циклов длины 5. Как видно из рис. 2, количество таких циклов совпадает с числом способов расставить цифры от 1 до 5 в вершинах правильного пятиугольника. При этом два способа считаются одинаковыми, если один может быть получен из другого некоторым поворотом пятиугольника вокруг своего центра.

Поставим в некоторую вершину пятиугольника цифру 1 (в какую именно — не важно, поскольку мы можем вращать пятиугольник). Тогда в соседнюю по часовой стрелке вершину можно поставить любую из четырёх оставшихся цифр: 1, 2, 3 или 4. Вне зависимости от того, какую цифру мы выберем, в следующую по часовой стрелке вершину мы можем поставить одну из трёх оставшихся. Оставшиеся две позиции можно занять оставшимися двумя цифрами ровно двумя способами. Итого, всего вариантов расстановки цифр по вершинам пятиугольника 4 · 3 · 2 = 24.

Теперь найдём количество различных объединений циклов длины 2 и 3. Цикл длины 2 можно составить 10 различными способами. В самом деле, этот цикл составляют две цифры; первую из них можно выбрать пятью способами (берём любую цифру от 1 до 5), а вторую — четырьмя (так как выбираем из оставшихся четырёх цифр); всего 5 · 4 = 20. Однако для нас нет разницы, в каком порядке выбирать цифры. То есть если мы сначала выберем 1, а потом 2, то это будет тот же самый способ организовать цикл, как если бы мы сначала выбрали 2, а потом 1. Потому что и то, и другое означает, что письмо, предназначенное первому знакомому, отправилось второму знакомому, а письмо, предназначенное второму знакомому, отправилось первому знакомому. Значит, найденное число надо разделить на 2.

Итак, разных циклов длины 2 может быть ровно 10. Для каждого из этих циклов не вошедшие в него три цифры образуют цикл длины 3. А так как из трёх цифр цикл длины 3 можно организовать двумя способами, то общее количество объединений циклов длины 2 и 3 равно 10 · 2 = 20.

Итого, общее число способов, которыми Катя могла сделать полную путаницу, равно 24 + 20 = 44.

б) Для того чтобы доказать формулу F_n = (n – 1)(F_n–1 + F_n–2), проследим судьбу первого письма. Предположим, оно попало k-му знакомому. Зададимся вопросом: кто же тогда получил k-е письмо? Здесь возможны два варианта.

1. Если k-е письмо получил первый знакомый, то в графической интерпретации условия 1-й и k-й знакомые образуют цикл длины 2. Таким образом, остальных знакомых можно рассматривать независимо от этого цикла, и сделать полную путаницу для них можно F_n–2 способами. Учитывая, что k-го знакомого можно выбрать (n – 1) способами (потому что это любой из n Катиных знакомых, кроме первого), общее количество возможностей сделать полную путаницу первым вариантом равно (n – 1)F_n–2.

2. Если k-е письмо попало не к 1-му знакомому, то эта ситуация аналогична исходной задаче для (n – 1)-го человека, если рассматривать письма со 2-го по n-е и считать, что для всех m ≠ k m-е письмо предназначалось m-му знакомому, а k-е письмо предназначалось 1-му знакомому. Всего таких способов F_n–1, а учитывая, что k-го знакомого можно выбрать (n – 1) способами, общее количество возможностей сделать полную путаницу вторым вариантом равно (n – 1)F_n–1.

Суммируя полученные результаты, мы имеем в точности F_n = (n – 1)(F_n–1 + F_n–2). Поскольку F₁ = 0, а F₂ = 1, осталось применить доказанную формулу 13 раз. Вот что получится: F₃ = 2; F₄ = 9; F₅ = 44; F₆ = 265; F₇ = 1854; F₈ = 14 833; F₉ = 133 496; F₁₀ = 1 334 961; F₁₁ = 14 684 570; F₁₂ = 176 214 841; F₁₃ = 2 290 792 932; F₁₄ = 32 071 101 049; F₁₅ = 481 066 515 734.

Ответ:
а) 44;
б) 481 066 515 734.

Задача о письмах, по-видимому, впервые упоминается в сочинениях французского математика Пьера де Монмора (Pierre Rémond de Montmort, 1678–1719). Монмор занимался исследованием азартных игр с точки зрения математики — деятельностью, при определённых обстоятельствах весьма выгодной. Подобные изыскания были начаты ранее Пьером Ферма (1601–1665) и Блезом Паскалем (1623–1662), и сейчас мы со всей определённостью можем сказать, что именно они положили начало современной теории вероятностей.

С точки зрения азартных игр, наша задача может быть сформулирована следующим образом. Допустим, что две колоды карт, одну из которых заранее хорошенько перетасовали, сравниваются карта за картой. Какова вероятность того, что, открывая одновременно в обеих колодах карту за картой, мы не встретим ни одного совпадения?

Как это принято в науке, вероятностью мы считаем отношение числа благоприятных исходов к общему числу исходов. В нашем случае каждый исход задаётся расположением карт в хорошо перетасованной колоде. Общее число исходов (то есть количество способов расположить карты в колоде) для колоды из 52 карт равно произведению всех натуральных чисел от 1 до 52. В самом деле, на первое место мы можем поставить одну из 52 карт, на второе место — одну из оставшихся 51 карты, и так далее. Для произведения натуральных чисел от 1 до n зарезервировано специальное обозначение: n! — читается n-факториал. Таким образом, вероятность не встретить ни одного совпадения равна .

Полученная нами дробь не даёт прямого ответа на вопрос, насколько эта вероятность велика. Правда ли, например, что она больше, чем 1/2, то есть что мы скорее не встретим ни одного совпадения, чем встретим хотя бы одно? К счастью, для числа F_n оказывается возможным вывести явную формулу. Именно, при помощи принципа включения-исключения можно доказать, что

   (1)

Отсюда, кстати, следует, что F_n = n·F_n–1 + (–1)ⁿ. Ну а найденная нами вероятность равна

   (2)

Знакомый с математическим анализом читатель сразу скажет, что в правой части формулы (2) стоит не что иное, как начальный кусок ряда Тейлора для экспоненты в точке x = –1. Отсюда вытекает, что искомую вероятность мы можем с большой точностью считать равной числу e^–1 = 0,367879... (погрешность не превышает 10^–69). Таким образом, в 6 случаях из 10, открывая одновременно в двух колодах карту за картой, мы в какой-то момент наткнёмся на две одинаковые карты. По той же причине можно надеяться, что хотя бы кто-то из Катиных знакомых получит письмо, адресованное именно ему. Как показывают изложенные выше рассуждения, надежды эти небезосновательны.

При подготовке материала была использована книга:
У. Болл и Г. Коксетер «Математические эссе и развлечения» (стр. 57–58).